﻿// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

/*=============================================================================
**
**
** Purpose: A circular-array implementation of a generic queue.
**
**
=============================================================================*/

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
using System.Threading;

namespace CuteAnt.Collections
{
  // A simple Queue of generic objects.  Internally it is implemented as a 
  // circular buffer, so Enqueue can be O(n).  Dequeue is O(1).
  [DebuggerTypeProxy(typeof(QueueDebugView<>))]
  [DebuggerDisplay("Count = {Count}")]
  [Serializable]
  public partial class QueueX<T> : IEnumerable<T>,
      System.Collections.ICollection,
      IReadOnlyCollection<T>
  {
    private T[] _array;
    private int _head;       // The index from which to dequeue if the queue isn't empty.
    private int _tail;       // The index at which to enqueue if the queue isn't full.
    private int _size;       // Number of elements.
    private int _version;
    [NonSerialized]
    private object _syncRoot;

    private const int MinimumGrow = 4;
    private const int GrowFactor = 200;  // double each time

    // Creates a queue with room for capacity objects. The default initial
    // capacity and grow factor are used.
    public QueueX()
    {
      _array = EmptyArray<T>.Instance; // Array.Empty<T>();
    }

    // Creates a queue with room for capacity objects. The default grow factor
    // is used.
    public QueueX(int capacity)
    {
      if (capacity < 0)
        throw new ArgumentOutOfRangeException(nameof(capacity), capacity, SR.ArgumentOutOfRange_NeedNonNegNum);
      _array = new T[capacity];
    }

    // Fills a Queue with the elements of an ICollection.  Uses the enumerator
    // to get each of the elements.
    public QueueX(IEnumerable<T> collection)
    {
      if (collection == null)
        throw new ArgumentNullException(nameof(collection));

      _array = EnumerableHelpers.ToArray(collection, out _size);
      if (_size != _array.Length) _tail = _size;
    }

    public int Count
    {
      get { return _size; }
    }

    bool ICollection.IsSynchronized
    {
      get { return false; }
    }

    object ICollection.SyncRoot
    {
      get
      {
        if (_syncRoot == null)
        {
          Interlocked.CompareExchange<object>(ref _syncRoot, new object(), null);
        }
        return _syncRoot;
      }
    }

    // Removes all Objects from the queue.
    public void Clear()
    {
      if (_size != 0)
      {
#if NETCOREAPP
        if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
        {
#endif
        if (_head < _tail)
        {
          Array.Clear(_array, _head, _size);
        }
        else
        {
          Array.Clear(_array, _head, _array.Length - _head);
          Array.Clear(_array, 0, _tail);
        }
#if NETCOREAPP
        }
#endif

        _size = 0;
      }

      _head = 0;
      _tail = 0;
      _version++;
    }

    // CopyTo copies a collection into an Array, starting at a particular
    // index into the array.
    public void CopyTo(T[] array, int arrayIndex)
    {
      if (array == null)
      {
        throw new ArgumentNullException(nameof(array));
      }

      if (arrayIndex < 0 || arrayIndex > array.Length)
      {
        throw new ArgumentOutOfRangeException(nameof(arrayIndex), arrayIndex, SR.ArgumentOutOfRange_Index);
      }

      int arrayLen = array.Length;
      if (arrayLen - arrayIndex < _size)
      {
        throw new ArgumentException(SR.Argument_InvalidOffLen);
      }

      int numToCopy = _size;
      if (numToCopy == 0) return;

      int firstPart = Math.Min(_array.Length - _head, numToCopy);
      Array.Copy(_array, _head, array, arrayIndex, firstPart);
      numToCopy -= firstPart;
      if (numToCopy > 0)
      {
        Array.Copy(_array, 0, array, arrayIndex + _array.Length - _head, numToCopy);
      }
    }

    void ICollection.CopyTo(Array array, int index)
    {
      if (array == null)
      {
        throw new ArgumentNullException(nameof(array));
      }

      if (array.Rank != 1)
      {
        throw new ArgumentException(SR.Arg_RankMultiDimNotSupported, nameof(array));
      }

      if (array.GetLowerBound(0) != 0)
      {
        throw new ArgumentException(SR.Arg_NonZeroLowerBound, nameof(array));
      }

      int arrayLen = array.Length;
      if (index < 0 || index > arrayLen)
      {
        throw new ArgumentOutOfRangeException(nameof(index), index, SR.ArgumentOutOfRange_Index);
      }

      if (arrayLen - index < _size)
      {
        throw new ArgumentException(SR.Argument_InvalidOffLen);
      }

      int numToCopy = _size;
      if (numToCopy == 0) return;

      try
      {
        int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;
        Array.Copy(_array, _head, array, index, firstPart);
        numToCopy -= firstPart;

        if (numToCopy > 0)
        {
          Array.Copy(_array, 0, array, index + _array.Length - _head, numToCopy);
        }
      }
      catch (ArrayTypeMismatchException)
      {
        throw new ArgumentException(SR.Argument_InvalidArrayType, nameof(array));
      }
    }

    // Adds item to the tail of the queue.
    public void Enqueue(T item)
    {
      if (_size == _array.Length)
      {
        int newcapacity = (int)((long)_array.Length * (long)GrowFactor / 100);
        if (newcapacity < _array.Length + MinimumGrow)
        {
          newcapacity = _array.Length + MinimumGrow;
        }
        SetCapacity(newcapacity);
      }

      _array[_tail] = item;
      MoveNext(ref _tail);
      _size++;
      _version++;
    }

    // GetEnumerator returns an IEnumerator over this Queue.  This
    // Enumerator will support removing.
    public Enumerator GetEnumerator()
    {
      return new Enumerator(this);
    }

    /// <internalonly/>
    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
      return new Enumerator(this);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
      return new Enumerator(this);
    }

    // Removes the object at the head of the queue and returns it. If the queue
    // is empty, this method throws an 
    // InvalidOperationException.
    public T Dequeue()
    {
      if (_size == 0)
      {
        ThrowForEmptyQueue();
      }

      int head = _head;
      T[] array = _array;

      T removed = array[head];
#if NETCOREAPP
      if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
      {
        array[head] = default;
      }
#else
      array[head] = default;
#endif
      MoveNext(ref _head);
      _size--;
      _version++;
      return removed;
    }

    public bool TryDequeue(out T result)
    {
      if (_size == 0)
      {
        result = default;
        return false;
      }

      int head = _head;
      T[] array = _array;

      result = array[head];
#if NETCOREAPP
      if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
      {
        array[head] = default;
      }
#else
      array[head] = default;
#endif
      MoveNext(ref _head);
      _size--;
      _version++;
      return true;
    }

    // Returns the object at the head of the queue. The object remains in the
    // queue. If the queue is empty, this method throws an 
    // InvalidOperationException.
    public T Peek()
    {
      if (_size == 0)
      {
        ThrowForEmptyQueue();
      }

      return _array[_head];
    }

    public bool TryPeek(out T result)
    {
      if (_size == 0)
      {
        result = default(T);
        return false;
      }

      result = _array[_head];
      return true;
    }

    // Returns true if the queue contains at least one object equal to item.
    // Equality is determined using EqualityComparer<T>.Default.Equals().
    public bool Contains(T item)
    {
      if (_size == 0)
      {
        return false;
      }

      if (_head < _tail)
      {
        return Array.IndexOf(_array, item, _head, _size) >= 0;
      }

      // We've wrapped around. Check both partitions, the least recently enqueued first.
      return
          Array.IndexOf(_array, item, _head, _array.Length - _head) >= 0 ||
          Array.IndexOf(_array, item, 0, _tail) >= 0;
    }

    // Iterates over the objects in the queue, returning an array of the
    // objects in the Queue, or an empty array if the queue is empty.
    // The order of elements in the array is first in to last in, the same
    // order produced by successive calls to Dequeue.
    public T[] ToArray()
    {
      if (_size == 0)
      {
        return EmptyArray<T>.Instance; // Array.Empty<T>();
      }

      T[] arr = new T[_size];

      if (_head < _tail)
      {
        Array.Copy(_array, _head, arr, 0, _size);
      }
      else
      {
        Array.Copy(_array, _head, arr, 0, _array.Length - _head);
        Array.Copy(_array, 0, arr, _array.Length - _head, _tail);
      }

      return arr;
    }

    // PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity
    // must be >= _size.
    private void SetCapacity(int capacity)
    {
      T[] newarray = new T[capacity];
      if (_size > 0)
      {
        if (_head < _tail)
        {
          Array.Copy(_array, _head, newarray, 0, _size);
        }
        else
        {
          Array.Copy(_array, _head, newarray, 0, _array.Length - _head);
          Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);
        }
      }

      _array = newarray;
      _head = 0;
      _tail = (_size == capacity) ? 0 : _size;
      _version++;
    }

    // Increments the index wrapping it if necessary.
    [MethodImpl(InlineMethod.Value)]
    private void MoveNext(ref int index)
    {
      // It is tempting to use the remainder operator here but it is actually much slower
      // than a simple comparison and a rarely taken branch.
      // JIT produces better code than with ternary operator ?:
      int tmp = index + 1;
      if (tmp == _array.Length)
      {
        tmp = 0;
      }
      index = tmp;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static void ThrowForEmptyQueue()
    {
      throw GetInvalidOperationException();
      InvalidOperationException GetInvalidOperationException()
      {
        return new InvalidOperationException(SR.InvalidOperation_EmptyQueue);
      }
    }

    public void TrimExcess()
    {
      int threshold = (int)(((double)_array.Length) * 0.9);
      if (_size < threshold)
      {
        SetCapacity(_size);
      }
    }

    // Implements an enumerator for a Queue.  The enumerator uses the
    // internal version number of the list to ensure that no modifications are
    // made to the list while an enumeration is in progress.
    [SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes", Justification = "not an expected scenario")]
    public struct Enumerator : IEnumerator<T>,
        System.Collections.IEnumerator
    {
      private readonly QueueX<T> _q;
      private readonly int _version;
      private int _index;   // -1 = not started, -2 = ended/disposed
      private T _currentElement;

      internal Enumerator(QueueX<T> q)
      {
        _q = q;
        _version = q._version;
        _index = -1;
        _currentElement = default(T);
      }

      public void Dispose()
      {
        _index = -2;
        _currentElement = default(T);
      }

      public bool MoveNext()
      {
        if (_version != _q._version) ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();

        if (_index == -2)
          return false;

        _index++;

        if (_index == _q._size)
        {
          // We've run past the last element
          _index = -2;
          _currentElement = default(T);
          return false;
        }

        // Cache some fields in locals to decrease code size
        T[] array = _q._array;
        int capacity = array.Length;

        // _index represents the 0-based index into the queue, however the queue
        // doesn't have to start from 0 and it may not even be stored contiguously in memory.

        int arrayIndex = _q._head + _index; // this is the actual index into the queue's backing array
        if (arrayIndex >= capacity)
        {
          // NOTE: Originally we were using the modulo operator here, however
          // on Intel processors it has a very high instruction latency which
          // was slowing down the loop quite a bit.
          // Replacing it with simple comparison/subtraction operations sped up
          // the average foreach loop by 2x.

          arrayIndex -= capacity; // wrap around if needed
        }

        _currentElement = array[arrayIndex];
        return true;
      }

      public T Current
      {
        get
        {
          if (_index < 0)
            ThrowEnumerationNotStartedOrEnded(_index);
          return _currentElement;
        }
      }

      [MethodImpl(MethodImplOptions.NoInlining)]
      private static void ThrowEnumerationNotStartedOrEnded(int index)
      {
        Debug.Assert(index == -1 || index == -2);
        throw GetInvalidOperationException();
        InvalidOperationException GetInvalidOperationException()
        {
          return new InvalidOperationException(index == -1 ? SR.InvalidOperation_EnumNotStarted : SR.InvalidOperation_EnumEnded);
        }
      }

      object IEnumerator.Current
      {
        get { return Current; }
      }

      void IEnumerator.Reset()
      {
        if (_version != _q._version) ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
        _index = -1;
        _currentElement = default(T);
      }
    }
  }
}
